The relationship between run-time performance and effective use of a processor's register set is well understood in the art. The allocation of registers to particular values during program execution can have a significant impact on execution efficiency. If a frequently manipulated value is not stored in a register, the processor must wait for access to a lower-level memory before operating on that value, and execution times will suffer. On the other hand, if an infrequently used value is stored in a register during times when in it not needed, that register cannot be allocated to a currently active value, also causing a decrease in execution efficiency.
Popular techniques for performing register allocation in a compiler are based on a graph coloring paradigm. In general, in using this technique, the register allocation portion of a compiler is applied to intermediate code that references an unlimited number of registers referred to as virtual registers. A single virtual register can have several distinct values that are live in different parts of the program being compiled. A value is deemed be live if it has been computed or defined and the value will be subsequently used in a computation before being recomputed or redefined. The period of time during program execution between when a value becomes live and when it is no longer live is called the live range of that value. The register allocator discovers all of the separate live ranges of the program and attempts to allocate them to physical registers of the target processor.
During the register allocation process, an interference graph is constructed from the code being compiled such that each node in the graph represents a value that may be stored in a register. Two nodes of the graph are connected by an edge if the values of those nodes interfere with each other. Two values interfere with each other if they are different, and one is live at the point where the other is defined. If a node has N edges, that node is said to be of degree N.
Once the interference graph is constructed, an attempt is made to color the graphs with K colors, where K is the number of processor registers available. The coloring of the interference graph is a process of assigning a color to each of the nodes in the graph such that if two nodes are connected by an edge, they are assigned different colors. If a K-coloring is found, each register is assigned a color, and live range nodes of that color are stored in the corresponding register during program execution. If a K-coloring does not exist, code must be added to the program to spill one or more live ranges, that is, provision must be made for certain values to be removed from registers during portions of program execution, and reloaded when such values are referenced again. This has the effect of eliminating the spilled live range and creating a new, small live range around each individual use or definition of that value within the program. The interference graph is transformed into one having additional nodes, but possibly fewer edges, and hopefully fewer interferences. Then the register allocator will attempt to K-color the new interference graph. This iterative process of spilling and attempting to K-color the resulting graph continues until a K-colorable graph is found.
The problem of obtaining a minimal graph coloring is an NP-complete problem. The time required to determine a graph coloring may be exponentially proportional to the size of the graph, which is impractical for the compilation process. Different heuristic approaches have been developed to create graph coloring register allocation schemes that are solvable in time linearly proportional to the size of the graph. Many of these schemes are based on the principle that if a node N has less than K neighbors, then no matter how the neighbors of N (those nodes connected to N by edges) are colored, there is necessarily one of the K colors left for node N. Thus, node N can be removed from the graph. The problem of obtaining a K-coloring of the interference graph is therefore recursively reduced to the problem of obtaining a K-coloring of a graph with one less node and probably several less edges.
One such prior art scheme has three phases. In the first phase, an interference graph is constructed. In the second phase, the graph is simplified by removing, one at a time, each node N with degree less than K, along with all of its edges, and placing the node N in a stack. If the allocator reaches a state where all remaining nodes have degree greater than or equal to K, it selects a node to spill. Using some metric, it chooses a node to spill, removes it from the graph, records that this node will be spilled, and continues with the second phase.
For the node that is to be spilled, the original program must be modified to include spill code that instructs the processor to store the spilled value in memory after definition, and restore the value to a register before it is used. Once the program has modified, the allocation process returns to the first phase, building an interference graph for the modified program and attempting to find a K-coloring for the new graph. When the allocator has modified the program sufficiently to permit a K-coloring, it proceeds to the third phase in which colors are assigned to the nodes in the stack.
In the second phase, the register allocator must decide which nodes to spill based on some metric. One possible metric is to choose the node with the lowest ratio of spill cost to degree. The spill cost is the number of additional cycles required to save and restore the live range. Or, alternatively, the spill cost can be estimated as the number of loads and stores that would be inserted in the program, weighted by the loop nesting depth of each insertion point. The spill cost may be precomputed for each node, so that when the register allocator reaches the point where it must choose a node to spill, it can divide the precomputed spill cost for each candidate node by that node's current degree. The candidate node with the lowest ratio is spilled.
In the third phase, the register allocator removes a node from the top of the stack created in phase 2 and reinserts it in the graph, along with all of its edges. The node is then assigned a color different from each of its neighbors. In theory, this coloring process should succeed given the work done in the second phase.
The above scheme is not guaranteed to find the minimal coloring for a given interference graph. In other words, it may insert spill code where it is not strictly necessary. An improvement to this scheme, often referred to as an optimistic allocator, enhances the likelihood of finding the minimal coloring. In this optimistic register allocation method, again an interference graph is constructed. During the simplification process, nodes are removed from the graphs in order of increasing degree. This simplification process differs from the first scheme in that instead of removing any node that has degree less than or equal to K, at each step the remaining node with the lowest degree is removed. No node is designated to be spilled. Once all of the nodes have been removed, the coloring phase is executed. The allocator rebuilds the graph by reinserting each node and its associated edges in the reverse order of removal. As each node is inserted, it is colored with the first color that does not appear in any of its neighbors. When a node is encountered that has neighbors with each of the possible colors, the allocator spills that node. This is handled by reinserting the node without assigning a color. The allocator continues to reinsert the remainder of the nodes and give them colors where possible. After the graph has been rebuilt, the allocator inserts spill code, builds a new interference graph, and returns to the simplification phase.
This method is further improved by taking into account spill cost when removing nodes from the graph. During the simplification phase, as nodes are selected for removal, nodes with the minimum ratio of spill cost to degree are removed first. In particular, when simplifying the interference graph, the allocator removes the nodes with degree less than K in arbitrary order, but when removing nodes with degree greater than or equal to K, the nodes are removed in order of increasing spill cost. Ordering the nodes this way determines the order in which the nodes will be colored in the area of a possible spill. Thus, this allocation scheme will spill either a subset of the live ranges of the previous allocation scheme or the same live ranges.